﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectEulerSolutions
{
    /*
     * It is possible to write five as a sum in exactly six different ways:

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

How many different ways can one hundred be written as a sum of at least two positive integers?

     * */
    class Problem76 : IProblem
    {
        int limit = 100;

        public string Calculate()
        {
            //ziva sila == 40 sekundi
            int count = CountCombinations(limit, limit - 1);

            return count.ToString();
        }

        public int CountCombinations(int n, int max)
        {
            int count = 0;
            for (int i = (n <= max ? n : max); i > 0; i--)
            {
                int remaining = n - i;

                if (remaining > 0)
                {
                    if (remaining <= i)
                        count++;
                    count += CountCombinations(remaining, i);
                }
            }
            return count;
        }
    }
}
